home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 2000 November: Tool Chest / Dev.CD Nov 00 TC Disk 2.toast / pc / sample code / processes / mp threaded sort / quicksort.cp < prev    next >
Encoding:
Text File  |  2000-09-28  |  3.7 KB  |  152 lines
  1. /*
  2.     File:        QuickSort.cp
  3.  
  4.     Contains:    fastQSort() is a replacement for qsort().  Compared with the Think C library
  5.                 version of qsort, fastQSort is about 3 times faster (it takes 1/3 the time), 
  6.                 and its speed isn't dependent on the data being sorted.
  7.     
  8.                 One problem with qsort is that when the data is not in random order -- for
  9.                 example when it's already ordered, in reverse order, or almost sorted -- then 
  10.                 qsort exhibits worst case behavior of N*N/2 operations.  For N=1024 this can 
  11.                 take about 30 seconds, instead of the usual 0.8 seconds.  The fastQSort 
  12.                 algorithm doesn't have this problem, because it randomly selects the pivot
  13.                 element, and so for N=1024 it requires about 0.26 secs +/- 0.02 secs.
  14.     
  15.                 Also, because fastQSort doesn't exhibit worst case behavior, it doesn't 
  16.                 require as much stack space, even though it has 12 bytes more of local
  17.                 variables.
  18.     
  19.                 The things that make fastQSort so much faster than qsort are:
  20.     
  21.             1)    fastQSort picks the pivot element randomly, so it doesn't display worst
  22.                 case behavior.
  23.         
  24.             2)    fastQSort uses pointers and pointer arithmetic, avoiding multiplication
  25.                 whenever possible.
  26.     
  27.             3)    qsort uses std_swap() to swap the data between two locations, and 
  28.                 std_swap loops through the data 3 times to perform the exchange!  In
  29.                 comparison, swapMem() loops through the data just once.
  30.         
  31.             4)    fastQSort uses register variables whenever it makes good sense to do so.
  32.     
  33.                 This version works within the shell of SortPicts.
  34.     
  35.         
  36.  
  37.     Written by: Haydn Huntley
  38.                 modified by Randy Thelen    
  39.  
  40.     Copyright:    Copyright © 1999 by Apple Computer, Inc., All Rights Reserved.
  41.  
  42.                 You may incorporate this Apple sample source code into your program(s) without
  43.                 restriction. This Apple sample source code has been provided "AS IS" and the
  44.                 responsibility for its operation is yours. You are not permitted to redistribute
  45.                 this Apple sample source code as "Apple sample source code" after having made
  46.                 changes. If you're going to re-distribute the source, we require that you make
  47.                 it clear in the source that the code was descended from Apple sample source
  48.                 code, but that you've made changes.
  49.  
  50.     Change History (most recent first):
  51.                 7/27/1999    Karl Groethe    Updated for Metrowerks Codewarror Pro 2.1
  52.                 
  53.  
  54. */
  55. #include "SortPicts.h"
  56.  
  57. void    QSort( SortPicts *sortPicts)
  58. {
  59.     sortPicts->QSort();
  60. }
  61.  
  62.  
  63. void    SortPicts::QSort( void)
  64. {
  65.         QuickSortEngine( 0, N);
  66. }
  67.  
  68.  
  69. void    SortPicts::ChooseMedian( long a, long b, long c)
  70. {
  71.     long        m;        //    median
  72.  
  73.     if( sortData[a] > sortData[b])
  74.         if( sortData[a] > sortData[c])
  75.             if( sortData[b] > sortData[c])
  76.                 m = b;
  77.             else
  78.                 m = c;
  79.         else
  80.             m = a;
  81.     else
  82.         if( sortData[a] > sortData[c])
  83.             m = a;
  84.         else
  85.             if( sortData[b] > sortData[c])
  86.                 m = c;
  87.             else
  88.                 m = b;
  89.     
  90.     if( a != m)
  91.         ExchangeSortItem( a, m);
  92. }
  93.  
  94.  
  95. void    SortPicts::QuickSortEngine( long left, long right)
  96. {
  97.     long            n;
  98.     long            i, j;
  99.     
  100.     while( (n = right - left) > 1)
  101.     {
  102.         if( n < kPivotCutoff)        //    Use a random pivot
  103.             ExchangeSortItem( left + Random( n), left);
  104.         else
  105.             ChooseMedian( left, left + (n >> 1), 
  106.                           left + Random( n));
  107.         
  108.         i = left;
  109.         j = right;
  110.         
  111.         while( 1)
  112.         {
  113.             i++;
  114.             while( (i < right) && (sortData[i] < sortData[left]))
  115.                 i++;
  116.             
  117.             j--;
  118.             while( (j > left) && (sortData[j] > sortData[left]))
  119.                 j--;
  120.             
  121.             if( i >= j)
  122.                 break;
  123.             
  124.             ExchangeSortItem( i, j);
  125.         }
  126.         
  127.         if( j == left)
  128.         {
  129.             left++;
  130.             continue;
  131.         }
  132.         
  133.         ExchangeSortItem( left, j);
  134.         if( (j - left) < (right - (j + 1)))
  135.         {
  136.             /* equivalent to doFastQSort (j + qSize, last);        */
  137.             /* to save stack space                                */
  138.             QuickSortEngine( left, j);
  139.             left = j + 1;
  140.         }
  141.         else
  142.         {
  143.             /* equivalent to doFastQSort (first, j);            */
  144.             /* to save stack space                                */
  145.             QuickSortEngine( j+1, right);
  146.             right = j;
  147.         }
  148.         
  149.     }
  150. }
  151.  
  152.